删除链表的节点

发表于 | 分类于 |
字数统计: 451 字 | 阅读时长 ≈ 1 分钟

题目描述：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

示例 1：

输入：head = [4,5,1,9], val = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入：head = [4,5,1,9], val = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
      
    }
}

方法一：单指针

首先需要处理头结点为空或者头结点即删除节点的情况，随后使用单指针循环找到要删除的节点，再修改对应节点的 next 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  public ListNode deleteNode(ListNode head, int val) {
    if(head == null) return null;
    if(head.val == val) return head.next;

    ListNode temp = head;
    while(temp.next != null && temp.next.val != val) {
      temp = temp.next;
    }
    if(temp.next != null) {
      temp.next = temp.next.next;
    }
    return head;
  }
}

复杂度分析：

  • 时间复杂度：O(N) ，N 为链表的长度，最坏情况下，要删除的结点位于链表末尾，这时我们需要遍历整个链表
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.1 MB, 在所有 Java 提交中击败了78.95%的用户